<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN">
<!-- Created by htmlize-1.16 in css mode. -->
<html>
  <head>
    <title>test.tex</title>
    <style type="text/css">
    <!--
      body {
        color: #000000;
        background-color: #f5deb3;
        font-weight: bold;
      }
      .comment {
        /* font-lock-comment-face */
        color: #b22222;
      }
      .constant {
        /* font-lock-constant-face */
        color: #5f9ea0;
      }
      .font-latex-math {
      }
      .font-latex-sedate {
      }
      .function-name {
        /* font-lock-function-name-face */
        color: #0000ff;
      }
      .hi-punc-purple2 {
      }
      .hi-punc-purple3 {
      }
      .keyword {
        /* font-lock-keyword-face */
        color: #a020f0;
      }
      .type {
        /* font-lock-type-face */
        color: #228b22;
      }
      a {
        color: inherit;
        background-color: inherit;
        font: inherit;
        text-decoration: inherit;
      }
      a:hover {
        text-decoration: underline;
      }
    -->
    </style>
  </head>
  <body>
    <pre>
<span class="comment">% Time</span><span class="hi-punc-purple3">-</span><span class="comment">stamp</span><span class="hi-punc-purple3">:</span><span class="comment"> </span><span class="hi-punc-purple3">&lt;</span><span class="comment">2004</span><span class="hi-punc-purple3">/</span><span class="comment">04</span><span class="hi-punc-purple3">/</span><span class="comment">06</span><span class="hi-punc-purple2">,</span><span class="comment"> 16</span><span class="hi-punc-purple3">:</span><span class="comment">46</span><span class="hi-punc-purple3">:</span><span class="comment">43 </span><span class="hi-punc-purple3">(</span><span class="comment">EST</span><span class="hi-punc-purple3">)</span><span class="hi-punc-purple2">,</span><span class="comment"> maverick</span><span class="hi-punc-purple2">,</span><span class="comment"> test</span><span class="hi-punc-purple2">.</span><span class="comment">tex</span><span class="hi-punc-purple3">&gt;</span><span class="comment">
</span><span class="font-latex-sedate"><span class="keyword">\subsection</span></span><span class="type"><span class="hi-punc-purple3">{</span></span><span class="type">Strict diagonal</span><span class="type"><span class="hi-punc-purple3">-</span></span><span class="type">dominance</span><span class="type"><span class="hi-punc-purple3">}</span></span>
Suppose we are given a matrix <span class="font-latex-math">$A</span><span class="hi-punc-purple3">=</span><span class="font-latex-math">L</span><span class="hi-punc-purple3">+</span><span class="font-latex-math">D$</span><span class="hi-punc-purple2">,</span> where <span class="font-latex-math">$L$</span> is a Laplacian and
<span class="font-latex-math">$D$</span> is a nonnegative diagonal matrix<span class="hi-punc-purple2">,</span> for which we seek to construct a
preconditioner<span class="hi-punc-purple2">.</span>
 
We may construct a Support Tree Preconditioner<span class="hi-punc-purple2">,</span> <span class="font-latex-math">$B </span><span class="hi-punc-purple3">=</span><span class="font-latex-math">
</span><span class="font-latex-sedate"><span class="keyword"><span class="font-latex-math">\begin</span></span></span><span class="function-name"><span class="hi-punc-purple3">{</span></span><span class="function-name"><span class="font-latex-math">pmatrix</span></span><span class="function-name"><span class="hi-punc-purple3">}</span></span><span class="font-latex-math"> T </span><span class="hi-punc-purple3">&amp;</span><span class="font-latex-math"> U\</span><span class="font-latex-sedate"><span class="font-latex-math">\U</span></span><span class="font-latex-sedate"><span class="font-latex-math">\TT</span></span><span class="font-latex-math"> </span><span class="hi-punc-purple3">&amp;</span><span class="font-latex-math"> W</span><span class="font-latex-sedate"><span class="keyword"><span class="font-latex-math">\end</span></span></span><span class="function-name"><span class="hi-punc-purple3">{</span></span><span class="function-name"><span class="font-latex-math">pmatrix</span></span><span class="function-name"><span class="hi-punc-purple3">}</span></span><span class="font-latex-math">$</span> for <span class="font-latex-math">$L$</span> and to use <span class="font-latex-math">$B</span><span class="hi-punc-purple2">'</span><span class="font-latex-math">
</span><span class="hi-punc-purple3">=</span><span class="font-latex-sedate"><span class="keyword"><span class="font-latex-math">\begin</span></span></span><span class="function-name"><span class="hi-punc-purple3">{</span></span><span class="function-name"><span class="font-latex-math">pmatrix</span></span><span class="function-name"><span class="hi-punc-purple3">}</span></span><span class="font-latex-math"> T </span><span class="hi-punc-purple3">&amp;</span><span class="font-latex-math"> U \</span><span class="font-latex-sedate"><span class="font-latex-math">\U</span></span><span class="font-latex-sedate"><span class="font-latex-math">\TT</span></span><span class="font-latex-math"> </span><span class="hi-punc-purple3">&amp;</span><span class="font-latex-math"> W</span><span class="hi-punc-purple3">+</span><span class="font-latex-math">D</span><span class="font-latex-sedate"><span class="keyword"><span class="font-latex-math">\end</span></span></span><span class="function-name"><span class="hi-punc-purple3">{</span></span><span class="function-name"><span class="font-latex-math">pmatrix</span></span><span class="function-name"><span class="hi-punc-purple3">}</span></span><span class="font-latex-math">$</span> as a preconditioner
for <span class="font-latex-math">$A$</span><span class="hi-punc-purple2">.</span>  If we let <span class="font-latex-math">$Q </span><span class="hi-punc-purple3">=</span><span class="font-latex-math"> W </span><span class="hi-punc-purple3">-</span><span class="font-latex-math"> U</span><span class="font-latex-sedate"><span class="font-latex-math">\TT</span></span><span class="font-latex-math"> T</span><span class="font-latex-sedate"><span class="font-latex-math">\IV</span></span><span class="font-latex-math"> U$</span><span class="hi-punc-purple2">,</span> by Lemma<span class="hi-punc-purple3">~</span><span class="font-latex-sedate"><span class="keyword">\ref</span></span><span class="constant"><span class="hi-punc-purple3">{</span></span><span class="constant">lem</span><span class="constant"><span class="hi-punc-purple3">:</span></span><span class="constant">stcg</span><span class="constant"><span class="hi-punc-purple3">}</span></span> it
suffices to bound <span class="font-latex-math">$</span><span class="font-latex-sedate"><span class="font-latex-math">\sigma</span></span><span class="hi-punc-purple3">(</span><span class="font-latex-math">A</span><span class="hi-punc-purple3">/</span><span class="font-latex-math">Q</span><span class="hi-punc-purple3">+</span><span class="font-latex-math">D</span><span class="hi-punc-purple3">)</span><span class="font-latex-math">$</span> and <span class="font-latex-math">$</span><span class="font-latex-sedate"><span class="font-latex-math">\sigma</span></span><span class="hi-punc-purple3">(</span><span class="font-latex-math">Q</span><span class="hi-punc-purple3">+</span><span class="font-latex-math">D</span><span class="hi-punc-purple3">/</span><span class="font-latex-math">A</span><span class="hi-punc-purple3">)</span><span class="font-latex-math">$</span><span class="hi-punc-purple2">.</span>

<span class="font-latex-sedate"><span class="keyword">\begin</span></span><span class="function-name"><span class="hi-punc-purple3">{</span></span><span class="function-name">proposition</span><span class="function-name"><span class="hi-punc-purple3">}</span></span><span class="font-latex-sedate"><span class="keyword">\label</span></span><span class="constant"><span class="hi-punc-purple3">{</span></span><span class="constant">prop</span><span class="constant"><span class="hi-punc-purple3">:</span></span><span class="constant">XZ</span><span class="constant"><span class="hi-punc-purple3">-</span></span><span class="constant">YZ</span><span class="constant"><span class="hi-punc-purple3">}</span></span>
If <span class="font-latex-math">$X$</span><span class="hi-punc-purple2">,</span> <span class="font-latex-math">$Y$</span><span class="hi-punc-purple2">,</span> and <span class="font-latex-math">$Z$</span> are spsd matrices of the same size then 
<span class="font-latex-math">$</span><span class="font-latex-sedate"><span class="font-latex-math">\sigma</span></span><span class="hi-punc-purple3">(</span><span class="font-latex-math">X</span><span class="hi-punc-purple3">+</span><span class="font-latex-math">Z</span><span class="hi-punc-purple3">/</span><span class="font-latex-math">Y</span><span class="hi-punc-purple3">+</span><span class="font-latex-math">Z</span><span class="hi-punc-purple3">)</span><span class="font-latex-math"> </span><span class="font-latex-sedate"><span class="font-latex-math">\leq</span></span><span class="font-latex-math"> </span><span class="font-latex-sedate"><span class="font-latex-math">\max</span></span><span class="font-latex-math">\</span><span class="hi-punc-purple3">{</span><span class="font-latex-sedate"><span class="font-latex-math">\sigma</span></span><span class="hi-punc-purple3">(</span><span class="font-latex-math">X</span><span class="hi-punc-purple3">/</span><span class="font-latex-math">Y</span><span class="hi-punc-purple3">)</span><span class="hi-punc-purple2">,</span><span class="font-latex-math">\</span><span class="hi-punc-purple2">,</span><span class="font-latex-math"> 1\</span><span class="hi-punc-purple3">}</span><span class="font-latex-math">$</span><span class="hi-punc-purple2">.</span>
<span class="font-latex-sedate"><span class="keyword">\end</span></span><span class="function-name"><span class="hi-punc-purple3">{</span></span><span class="function-name">proposition</span><span class="function-name"><span class="hi-punc-purple3">}</span></span>

<span class="font-latex-sedate">\Proof</span> We have <span class="font-latex-math">$</span><span class="font-latex-sedate"><span class="font-latex-math">\sigma</span></span><span class="hi-punc-purple3">(</span><span class="font-latex-math">X</span><span class="hi-punc-purple3">+</span><span class="font-latex-math">Z</span><span class="hi-punc-purple3">/</span><span class="font-latex-math">Y</span><span class="hi-punc-purple3">+</span><span class="font-latex-math">Z</span><span class="hi-punc-purple3">)</span><span class="font-latex-math"> </span><span class="hi-punc-purple3">=</span><span class="font-latex-math"> 
</span><span class="font-latex-sedate"><span class="font-latex-math">\min</span></span><span class="font-latex-math">\</span><span class="hi-punc-purple3">{</span><span class="font-latex-sedate"><span class="font-latex-math">\tau</span></span><span class="font-latex-math"> </span><span class="font-latex-sedate"><span class="font-latex-math">\mid</span></span><span class="font-latex-math"> </span><span class="font-latex-sedate"><span class="font-latex-math">\forall</span></span><span class="font-latex-sedate"><span class="font-latex-math">\vv</span></span><span class="hi-punc-purple3">{</span><span class="font-latex-math">x</span><span class="hi-punc-purple3">}</span><span class="hi-punc-purple2">,</span><span class="font-latex-math">\</span><span class="hi-punc-purple2">,</span><span class="font-latex-math"> </span><span class="font-latex-sedate"><span class="font-latex-math">\tau</span></span><span class="font-latex-sedate"><span class="font-latex-math">\cdot</span></span><span class="font-latex-math"> </span><span class="font-latex-sedate"><span class="font-latex-math">\vv</span></span><span class="hi-punc-purple3">{</span><span class="font-latex-math">x</span><span class="hi-punc-purple3">}</span><span class="font-latex-sedate"><span class="font-latex-math">\TT</span></span><span class="font-latex-math"> </span><span class="hi-punc-purple3">(</span><span class="font-latex-math">Y</span><span class="hi-punc-purple3">+</span><span class="font-latex-math">Z</span><span class="hi-punc-purple3">)</span><span class="font-latex-sedate"><span class="font-latex-math">\vv</span></span><span class="hi-punc-purple3">{</span><span class="font-latex-math">x</span><span class="hi-punc-purple3">}</span><span class="font-latex-math"> </span><span class="font-latex-sedate"><span class="font-latex-math">\geq</span></span><span class="font-latex-math">
       </span><span class="font-latex-sedate"><span class="font-latex-math">\vv</span></span><span class="hi-punc-purple3">{</span><span class="font-latex-math">x</span><span class="hi-punc-purple3">}</span><span class="font-latex-sedate"><span class="font-latex-math">\TT</span></span><span class="hi-punc-purple3">(</span><span class="font-latex-math">X</span><span class="hi-punc-purple3">+</span><span class="font-latex-math">Z</span><span class="hi-punc-purple3">)</span><span class="font-latex-sedate"><span class="font-latex-math">\vv</span></span><span class="hi-punc-purple3">{</span><span class="font-latex-math">x</span><span class="hi-punc-purple3">}</span><span class="font-latex-math">\</span><span class="hi-punc-purple3">}</span><span class="font-latex-math"> </span><span class="hi-punc-purple3">=</span><span class="font-latex-math"> 
</span><span class="font-latex-sedate"><span class="font-latex-math">\min</span></span><span class="font-latex-math">\</span><span class="hi-punc-purple3">{</span><span class="font-latex-sedate"><span class="font-latex-math">\tau</span></span><span class="font-latex-math"> </span><span class="font-latex-sedate"><span class="font-latex-math">\mid</span></span><span class="font-latex-math"> </span><span class="font-latex-sedate"><span class="font-latex-math">\forall</span></span><span class="font-latex-sedate"><span class="font-latex-math">\vv</span></span><span class="hi-punc-purple3">{</span><span class="font-latex-math">x</span><span class="hi-punc-purple3">}</span><span class="hi-punc-purple2">,</span><span class="font-latex-math">\</span><span class="hi-punc-purple2">,</span><span class="font-latex-math"> </span><span class="hi-punc-purple3">(</span><span class="font-latex-sedate"><span class="font-latex-math">\tau</span></span><span class="hi-punc-purple3">-</span><span class="font-latex-math">1</span><span class="hi-punc-purple3">)</span><span class="font-latex-sedate"><span class="font-latex-math">\cdot</span></span><span class="font-latex-math"> </span><span class="font-latex-sedate"><span class="font-latex-math">\vv</span></span><span class="hi-punc-purple3">{</span><span class="font-latex-math">x</span><span class="hi-punc-purple3">}</span><span class="font-latex-sedate"><span class="font-latex-math">\TT</span></span><span class="font-latex-math"> Z</span><span class="font-latex-sedate"><span class="font-latex-math">\vv</span></span><span class="hi-punc-purple3">{</span><span class="font-latex-math">x</span><span class="hi-punc-purple3">}</span><span class="font-latex-math"> </span><span class="hi-punc-purple3">+</span><span class="font-latex-math"> 
      </span><span class="font-latex-sedate"><span class="font-latex-math">\tau</span></span><span class="font-latex-math"> </span><span class="font-latex-sedate"><span class="font-latex-math">\cdot</span></span><span class="font-latex-sedate"><span class="font-latex-math">\vv</span></span><span class="hi-punc-purple3">{</span><span class="font-latex-math">x</span><span class="hi-punc-purple3">}</span><span class="font-latex-sedate"><span class="font-latex-math">\TT</span></span><span class="font-latex-math"> Y</span><span class="font-latex-sedate"><span class="font-latex-math">\vv</span></span><span class="hi-punc-purple3">{</span><span class="font-latex-math">x</span><span class="hi-punc-purple3">}</span><span class="font-latex-math"> </span><span class="font-latex-sedate"><span class="font-latex-math">\geq</span></span><span class="font-latex-math"> </span><span class="font-latex-sedate"><span class="font-latex-math">\vv</span></span><span class="hi-punc-purple3">{</span><span class="font-latex-math">x</span><span class="hi-punc-purple3">}</span><span class="font-latex-sedate"><span class="font-latex-math">\TT</span></span><span class="font-latex-math"> X</span><span class="font-latex-sedate"><span class="font-latex-math">\vv</span></span><span class="hi-punc-purple3">{</span><span class="font-latex-math">x</span><span class="hi-punc-purple3">}</span><span class="font-latex-math">\</span><span class="hi-punc-purple3">}</span><span class="font-latex-math"> </span><span class="font-latex-sedate"><span class="font-latex-math">\leq</span></span><span class="font-latex-math"> 
</span><span class="font-latex-sedate"><span class="font-latex-math">\max</span></span><span class="font-latex-math">\</span><span class="hi-punc-purple3">{</span><span class="font-latex-math">1</span><span class="hi-punc-purple2">,</span><span class="font-latex-math">\</span><span class="hi-punc-purple2">,</span><span class="font-latex-sedate"><span class="font-latex-math">\sigma</span></span><span class="hi-punc-purple3">(</span><span class="font-latex-math">X</span><span class="hi-punc-purple3">/</span><span class="font-latex-math">Y</span><span class="hi-punc-purple3">)</span><span class="font-latex-math">\</span><span class="hi-punc-purple3">}</span><span class="font-latex-math">$</span><span class="hi-punc-purple2">.</span><span class="font-latex-sedate">\QED</span>
</pre>
  </body>
</html>
